package targetToOffer.nintehDay;

import com.sun.org.apache.bcel.internal.generic.FieldGen;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

/**
 * @author Godc
 * @description
 */
public class Permutation {
    public static void main(String[] args) {
        PermutationSolution s = new PermutationSolution();
        String[] abcs = s.permutation("f");
        HashMap<Object, Object> map = new HashMap<>();
        for (int i = 0; i < abcs.length; i++) {
            System.out.println(abcs[i]);
        }
    }
}
class PermutationSolution {
    ArrayList<String> res = new ArrayList<>();
    StringBuffer buffer = new StringBuffer();
    public String[] permutation(String s) {
        int len = s.length();
        int[] visited = new int[len];
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        dfs(chars,visited,0,len);
        String[] strings = new String[res.size()];
        int x = 0;
        for (String re : res) {
            strings[x++] = re;
        }
        return strings;
    }
    public void dfs(char[] s,int[] visited,int step,int len){
        if(step==len){
            res.add(buffer.toString());
            return;
        }
        for (int i = 0;i<len;i++){
            if(i>0&&s[i]==s[i-1]&&visited[i-1]==0) continue;
            if(visited[i]==0){
                buffer.append(s[i]);
                visited[i] = 1;
                dfs(s,visited,step+1,len);
                buffer.deleteCharAt(buffer.length()-1);
                visited[i] = 0;
            }
        }
    }
}